---
title: "5、迷宫"
created: 2025-11-28
tags:
  - 算法
---

# 5、迷宫

## 题目 [迷宫](https://www.lanqiao.cn/paper/3842/problem/602/)

![[image-46dae9e3.png]]

```
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
```

## 思路分析

只需要在前面的基础上 加上一个char p[4]数组 分别对应四个方向的上左下右 并开一个pre[N][M]记录每个点是由上一个点从哪个方向走过来的
最后只需要 当找到终点的时候 回溯一下输出路径 如果该位置记录的UP 就说明该点是被上一个点向上走到的 所以回溯的时候使用 dfs(x+1,y)
往下找到上一个点

默认是可以固定成

```cpp
int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};
char p[4]={'U','R','D','L'};
char pre[N][M];

void print_path(int x,int y){

    if(x==0 && y==0)	return;

    if(pre[x][y]=='U')

       print_path(x+1,y);

    if(pre[x][y]=='R')

       print_path(x,y-1);

    if(pre[x][y]=='D')

       print_path(x-1,y);

    if(pre[x][y]=='L')

       print_path(x,y+1);

    cout<<pre[x][y];

}
```

因为要求输出字典序

所以这个拓展顺序得进行改变 不能是上右下左了

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef pair<int,int> PII;
const int N=35,M=55;
char g[N][M];
int d[N][M];
int n,m;

//int dx[4]={-1,0,1,0};
//int dy[4]={0,1,0,-1};
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
bool isVaild(int x,int y){
	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && d[x][y]==-1;
}
//char p[4]={'U','R','D','L'};
char p[4]={'D','L','R','U'};
char pre[N][M];

void print_path(int x,int y){
	if(x==0 && y==0)	return;
	if(pre[x][y]=='U')
		print_path(x+1,y);
	if(pre[x][y]=='R')
		print_path(x,y-1);
	if(pre[x][y]=='D')
		print_path(x-1,y);
	if(pre[x][y]=='L')
		print_path(x,y+1);
	cout<<pre[x][y];
}

void bfs(int x,int y){
	queue<PII> q;
	memset(d,-1,sizeof d);
	q.push({x,y});
	d[x][y]=0;

	while(!q.empty()){
		auto cur=q.front();q.pop();
		int ux=cur.first,uy=cur.second;

		if(ux==n-1 && uy==m-1){
			print_path(ux,uy);
			return;
		}

		for(int i=0;i<4;i++){
			int nx=ux+dx[i],ny=uy+dy[i];
			if(isVaild(nx,ny) && g[nx][ny]=='0'){
				q.push({nx,ny});
				d[nx][ny]=d[ux][uy]+1;
				pre[nx][ny]=p[i];
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=30,m=50;
	for(int i=0;i<n;i++)
		cin>>g[i];
	bfs(0,0);
	return 0;
 }
```

## 同类题型

## 视频讲解

---
⬅️ [[4、数的分解|4、数的分解]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/历年真题 模考特训/第十届 c++ B组 省赛/6、特别数的和|6、特别数的和]]